import collections
import itertools
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        #collections.Counter()用于统计字符串word中每个字母所占的个数
        #itertools.chain()用于将字符串数组中的每个字符串打碎成字母 例如将["abc","bd"]打碎成["a","b","c","b","d"]
        if collections.Counter(word) - collections.Counter(itertools.chain(*board)):#用于判断字符矩阵中是否包含足够数量的目标字符串中的字母
            return False
        m, n, l = len(board), len(board[0]), len(word) #m为字符串数组中字符串的个数，n为数组中第一个字符串的长度，l为目标字符串的长度
        d = ((0, 1), (1, 0), (0, -1), (-1, 0))  #定义四个方向向量
        def f(i, j, t): #此函数用于验证目标字符串中的第t个字母是否对应
            if t == l - 1:
                return board[i][j] == word[-1]
            v, board[i][j] = board[i][j], ''
            # any() 函数用于判断给定的可迭代参数 iterable 是否全部为 False，则返回 False，如果有一个为 True，则返回 True。
            # 元素除了是 0、空、FALSE 外都算 TRUE。
            return any(
                0 <= (x := i + r) < m and \
                0 <= (y := j + c) < n and \
                board[x][y] == word[t + 1] and \
                f(x, y, t + 1)
                for r, c in d   #r,c分别为方向向量的横纵坐标
            ) or board[i].__setitem__(j, v)
            #_setitem__:每当属性被赋值的时候都会调用该方法，因此不能再该方法内赋值 self.name = value 会死循环
        return any(
            f(i, j, 0) 
            #itertools.product：类似于求多个可迭代对象的笛卡尔积。
            for i, j in itertools.product(range(m), range(n)) 
            if board[i][j] == word[0]
        )


board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word="ABCCED"
s=Solution()
print(s.exist(board,word))